package org.example.algorithm.stack;

import java.util.ArrayDeque;
import java.util.Deque;

//32. 最长有效括号
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
public class LongestValidParenthesesSolution {

    public static void main(String[] args) {
        String s = ")()())";
        LongestValidParenthesesSolution solution = new LongestValidParenthesesSolution();
        int ans = solution.longestValidParentheses(s);
        System.out.println(ans);
    }

    //dp解法()()(())

    public int longestValidParentheses(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        int ans = 0;
        int[] dp = new int[len];
        for (int i=1;i<len;i=i+1) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i-1) == '(') {
                    dp[i] = (i>=2 ? dp[i-2] : 0) + 2;
                } else if (s.charAt(i-1) == ')' && i-dp[i-1]-1 >=0 && s.charAt(i-dp[i-1]-1) == '(') {
                    dp[i] = dp[i-1] + (i-dp[i-1]-2 >=0 ? dp[i-dp[i-1]-2] : 0) + 2;
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    //暴力解法(部分用例超时)
    public int longestValidParentheses1(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        int start = len % 2 == 0 ? len : len-1;
        for (int i=start;i>=2;i=i-2) {
            for (int j=0;j+i-1<len;j++) {
                if (isValid(s, j, j+i-1)) {
                    return i;
                }
            }
        }
        return 0;
    }

    private boolean isValid(String s, int start, int end) {
        Deque<Character> stack = new ArrayDeque<>();
        for (int i=start;i<=end;i++) {
            if (s.charAt(i) == '(') {
                stack.push('(');
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }



    //正反遍历
    public int longestValidParentheses3(String s) {
        int left = 0;
        int right = 0;
        int maxLen = 0;
        //正序遍历一次
        for (int i=0;i<s.length();i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxLen = Math.max(maxLen, 2*left);
            } else if (right > left) {
                left = 0;
                right = 0;
            }
        }
        left = 0;
        right = 0;
        //倒序遍历一次
        for (int i=s.length()-1;i>=0;i--) {
            if (s.charAt(i) == ')') {
                right++;
            } else {
                left++;
            }
            if (left == right) {
                maxLen = Math.max(maxLen, 2*left);
            } else if(left > right) {
                left = 0;
                right = 0;
            }
        }
        return maxLen;
    }

    //使用栈
    public int longestValidParentheses2(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        //用于计算匹配长度
        stack.push(-1);
        int maxLen = 0;
        int cur = 0;
        while (cur < len) {
            if (s.charAt(cur) == ')') {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(cur);
                } else {
                    maxLen = Math.max(maxLen, cur-stack.peek());
                }
            } else {
                stack.push(cur);
            }
            cur++;
        }
        return maxLen;
    }
}
